package it.storm.solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 665. 非递减数列
 * https://leetcode-cn.com/problems/non-decreasing-array/
 */
public class Solutions_665 {
    public static void main(String[] args) {
        int[] nums1 = {4, 2, 3};  // output: true
        int[] nums2 = {4, 2, 1};  // output: false
        int[] nums3 = {3, 4, 2, 3};  // output: false
        int[] nums4 = {5, 7, 1, 8};  // output: true
        int[] nums5 = {-1, 4, 2, 3};  // output: true

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);
        inputs.add(nums4);
        inputs.add(nums5);

        for (int[] input : inputs) {
            boolean result = checkPossibility(input);
            System.out.println(result);
        }
    }

    // 关键：当前元素小于前一元素时，需要改变为非递减序列
    // 改变时，分两种情况：是将当前元素改变为前一元素呢？还是将前一元素改变为当前元素？
    // 规则：若是改变前一元素为当前元素后，则前一元素小于其前一元素了，那么只能修改当前元素为前一元素，
    // 否则可以将前一元素改变为当前元素
    public static boolean checkPossibility(int[] nums) {
        int cnt = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= nums[i - 1]) {
                continue;
            }
            // 需要改变为非递减序列
            if (i > 1 && nums[i - 2] > nums[i]) {
                // 前一元素不变，改变当前元素为前一元素
                nums[i] = nums[i - 1];
            } else {
                // 当前元素不变，改变前一元素为当前元素
                nums[i - 1] = nums[i];
            }
            cnt ++;
            if (cnt > 1) {
                return false;
            }
        }
        return true;
    }
}
